package hotLeetcode;

import java.util.ArrayList;
import java.util.List;

public class H34Leetcode {
    public int[] searchRange2(int[] nums, int target) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                list.add(i);
            }

        }

        return convert(list);


    }

    private int[] convert(List<Integer> list) {
        if (list == null || list.isEmpty()) {
            return new int[]{-1, -1};
        }


        return new int[]{list.get(0), list.get(list.size() - 1)};
    }


    public int[] searchRange(int[] nums, int target) {
        int first = findFirst(nums, target);
        int last = findLast(nums, target);
        return new int[]{first, last};

    }

    private int findFirst(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int first = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                first = mid;
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return first;

    }

    private int findLast(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int last =   - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                last = mid;
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return last;

    }



}
